Problem A(小埋与Chicken rabbit with cages):
此题为典型的鸡兔同笼问题,原意用于照顾蒟蒻,故比较简单,模拟解方程组即可。
$ x+y=head $
$ 2x+4y=leg $
附标程:
1 |
|
Problem B(小埋与哥哥的企划):
采用深度优先搜索(DFS)算法,可以从两个角度出发:
(1) 以专家为出发点,每个专家要么选择他要么不选择他,当所有专家都确定是否选择后,这代表一种备选的方案,但是这个方案是否可行,需要检查是否所有n个问题都得到解决,在搜索的过程中记录最少的专家数。
(2) 以问题为出发点,每个问题都可能会有若干个专家可以解决该问题,依次尝试选择每个专家,然后继续下个问题,直到所有问题被解决。
我们考虑以第(2)个角度出发,尝试如何优化和剪枝,基本思想是:对于某个问题,如果只有一个专家能解决,则该专家是必选的,这是其中一个优化策略。对于尝试对某个问题选择专家时,如果当前已选择的专家数>=已记录的最少专家数-1,则表示即使选择该专家,其最终方案的专家数也不可能少于当前记录的最少专家数,因此不需要尝试选择该专家。
进一步的优化还可以这样做:在调用搜索函数前,检查每一位专家能解决的问题,如果该专家能解决的问题,另一位专家都能解决,则该专家不需要参与选择,即可以在数组中标志该专家为已选择(注意,虽然将他标志为已选择,但是该专家不计算在已选择专家数中),这样在递归搜索时其搜索的规模将会降低。
附标程(效率还是比较低):
1 |
|
Problem C(小埋与TSF的密信):
跟普通的加密解密字符一样,只不过这道题要多做一步:
统计!
根据大量的英文文章字母统计,绝大部分的文章中字母”e”,”E”出现得最多,因此可以在此入手。
先将输入的加密后的字符进行统计,找出出现得最多的字母,根据这个字母与”e”,”E”的关系,即可按照正常的思路进行解密。
附标程:
1 |
|